#include < iostream>

using namespace std;

class Solution
{
    // 0-2^16
public:
    int mySqrt(int x)
    {
        int min = 0, max = 2 << 16;
        //int minAns = 0, maxAns = 2 << 31 - 1;
        while (min!=max)
        {
            int mid = (min + max) / 2;
            int ans = mid * mid;
            if (ans <= x)
            {
                min = mid;
                //minAns = mid;
            }
            else
            {
                max = mid;
            }
        }
        return min;
    }
};

int main()
{
    Solution s;
    cout << s.mySqrt(8) << endl;
    return 0;
}